//
// Created by dengspc on 2019/1/29.
//

#ifndef INC_010_ALGORITHM_SPALYTREE_H
#define INC_010_ALGORITHM_SPALYTREE_H

#include <iostream>
#include <cassert>
#include <cmath>
using namespace std;

/**
 * https://baike.baidu.com/item/%E4%BC%B8%E5%B1%95%E6%A0%91/7003945?fr=aladdin
 * https://blog.csdn.net/canot/article/details/79968748
 * @tparam Key
 * @tparam Value
 */
template <typename Key,typename Value>
class SplayTree:public SearchTree<Key,Value>{
private:
    struct Node {
        Key key;
        Value value;
        Node *left = NULL;
        Node *right = NULL;
        int N = 1;
//        int height = 1;

        Node(Key key, Value value){
            this->key=key;
            this->value=value;
        }

        Node(const Node* node){
            this->key = node->key;
            this->value =  node->value;
//            if(node->left!=NULL) {
//                this->left = new Node(node->left);
//            }
//            if(node->right!=NULL) {
//                this->right = new Node(node->right);
//            }
            this->N = node->N;
        }
    };
    void destory(Node *node){
        if(node==NULL)
            return;
        destory(node->left);
        destory(node->right);
        delete node;
    }

    Node * root;
    Key spalytarget = NULL;//用于删除时候的旋转调整。

    Node* rotateLeft(Node * h){
        Node* x = h->right;
        h->right = x->left;
        x->left = h;

        x->N = h->N;
        h->N = 1+size(h->left)+size(h->right);

        return x;
    }

    Node* rotateRight(Node* h){
        Node* x = h->left;
        h->left = x->right;
        x->right = h;

        x->N = h->N;
        h->N = 1+size(h->left)+size(h->right);

        return x;
    }

    /**
     *  定义伸展树的旋转为逐层伸展
     * @param parent
     * @param key
     * @return
     */
    Node* _spaly1(Node* parent, Key key){
        Node* left = parent->left;

        if(left!=NULL && left->key==key){
            parent =  rotateRight(parent);
        }
        Node* right = parent->right;
        if(right!=NULL && right->key==key){
            parent = rotateLeft(parent);
        }
        parent->N = 1+size(parent->left)+size(parent->right);
        return parent;
    }

    /**
     * 定义伸展树的旋转为双层伸展
     * @param parent
     * @param key
     * @return
     */
    Node* _spaly2(Node* parent, Key key){
        Node* left = parent->left;
        Node* right = parent->right;
        if(left!=NULL){
            if(root==parent && left->key==key){
                parent = rotateRight(parent);
            }else{
                Key leftleft = left->left==NULL?NULL:left->left->key;
                Key leftright = left->right==NULL?NULL:left->right->key;
                if(key == leftleft){
                    parent = rotateRight(rotateRight(parent));
                }else if(key == leftright){
                    parent->left =  rotateLeft(parent->left);
                    parent = rotateRight(parent);
                }
            }
        }
        if(right!=NULL){
            if(root==parent && right->key==key){
                parent = rotateLeft(parent);
            }else {
                Key rightright = right->right == NULL ? NULL : right->right->key;
                Key rightleft = right->left == NULL ? NULL : right->left->key;
                if (key == rightright) {
                    parent = rotateLeft(rotateLeft(parent));
                } else if (key == rightleft) {
                    parent->right = rotateRight(parent->right);
                    parent = rotateLeft(parent);
                }
            }
        }
        parent->N = 1+size(parent->left)+size(parent->right);
        return parent;
    }

    int size(Node* node){
        if(node==NULL) return 0;
        return node->N;
    }

    Node* put(Node* node, Key key, Value value){
        if(node == NULL){
            return new Node(key,value);
        }
        if(node->key==key){
            node->value=value;
        }else if(node->key>key){
            node->left = put(node->left,key,value);
        }else{
            node->right = put(node->right,key,value);
        }
//        node = _spaly1(node,key);
        node = _spaly2(node,key);
        return node;
    }

    Node* _copy(Node* node){
        Node* nnode = new Node(node);
        if(node->left!=NULL) {
            nnode->left = _copy(node->left);
        }
        if(node->right!=NULL) {
            nnode->right = _copy(node->right);
        }
        return nnode;
    }

    Node* _search(Node * node, Key key){
        if(node == NULL)
            return NULL;
        if(node->key==key){
            return node;
        }
        if(node->key>key){
            node->left =  _search(node->left,key);
        }
        if(node->key<key){
            node->right =  _search(node->right,key);
        }
//        node =  _spaly1(node,key);
        node =  _spaly2(node,key);
        return node;
    }

    Node * _removeMin(Node* node){
        if(node->left==NULL) {
            Node* right = node->right;
            delete node;
            return right;
        }
        node->left = _removeMin(node->left);
//        node = _spaly1(node);
//        node = _spaly2(node);
        return node;
    }

    Node * _removeMax(Node* node){
        if(node->right==NULL) {
            Node* left = node->left;
            delete node;
            return left;
        }
        node->left = _removeMax(node->right);
//        node = _spaly1(node);
//        node = _spaly2(node);
        return node;
    }

    /**
     * Delete(x,S)：将元素x从伸展树S所表示的有序集中删除。
     *首先，用在二叉查找树中查找元素的方法找到x的位置。如果x没有孩子或只有一个孩子，那么直接将x删去，并通过Splay操作，
     * 将x节点的父节点调整到伸展树的根节点处。否则，则向下查找x的后继y，用y替代x的位置，最后执行Splay(y,S)，
     * 将y调整为伸展树的根。
     * @param node
     * @param key
     * @return
     */
    Node* _remove(Node* node, Key key){
        if(node == NULL)
            return NULL;
        if(node->key>key){
            if(node->left!=NULL && node->left->key==key){
                spalytarget = node->key;//这是调整目标
            }
            node->left=_remove(node->left,key);
        }else if(node->key<key){
            if(node->right!=NULL && node->right->key==key){
                spalytarget = node->key;//这是调整目标
            }
            node->right=_remove(node->right,key);
        }else{
            if(node->right==NULL && node->left==NULL){
                delete node;
                return NULL;
            }else if(node->right!=NULL && node->left==NULL){
                Node* succeed =  node->right;
                delete node;
                return succeed;
            }else if(node->left!=NULL && node->right==NULL){
                Node* succeed =  node->left;
                delete node;
                return succeed;
            }else{
                Node* succeed = _minNum(node->right);//取node后继,需要拷贝一份
                spalytarget = succeed->key;//这是调整目标
                node->key = succeed->key;
                node->value = succeed->value;
                node->right = _removeMin(node->right);
            }
        }
        if(spalytarget!=NULL) {
//          node = _spaly1(node,node->key);
            node = _spaly2(node, spalytarget);
        }
        return node;
    }

    Node* _join(Node* node){
        if(node!=NULL){
            _join(node->left);
            _join(node->right);
            root = put(root,node->key,node->value);
        }
        return root;
    }

    Node*  _maxNum(Node* node){
        while(node->right){
            node = node->right;
        }
        return node;
    }

    Node* _minNum(Node* node){
        while(node->left){
            node = node->left;
        }
        return node;
    }
    bool _contain(Node * node, Key key){
        if(node == NULL)
            return false;
        if(node->key==key){
            return true;
        }
        if(node->key>key){
            return _contain(node->left,key);
        }
        if(node->key<key){
            return _contain(node->right,key);
        }
    }

    bool _isBST(Node* node, Key low, Key high){
        if(node == NULL) return true;
        if(low!=NULL && node->key<=low) return false;
        if(high!=NULL && node->key>=high) return false;
        return _isBST(node->left,low,node->key) && _isBST(node->right,node->key,high);
    }

    bool _isSizeConsistent(Node* node){
        if(node == NULL) return true;
        if(node->N!=1+size(node->left)+size(node->right)) return false;
        return _isSizeConsistent(node->right) && _isSizeConsistent(node->left);
    }

    int _rank(Node* node, Key key){
        int rank = 0;
        while(node != NULL){
            int leftCount = node->left==NULL?0:node->left->N;
            if(node->key==key){
                return rank+leftCount;
            }else if(node->key<key){
                rank+=leftCount+1;
                node=node->right;
            }else{
                node=node->left;
            }
        }
        return rank;
    }

    /**
     *
     * @param node 当前节点
     * @param preRank 以node为根节点的树中最小节点的排名
     * @param select
     * @return
     */
    Node* _select(Node* node,int preRank,int select){
        int curentRank = (node->left==NULL?0:node->left->N)+preRank;
        if(select==curentRank){
            return node;
        }else if(select>curentRank){
            return _select(node->right,curentRank+1,select);
        }else{
            return _select(node->left,preRank,select);
        }
    }


public:
    SplayTree(){
        root = NULL;
    }
    ~SplayTree(){
        destory(root);
    }
    int size(){
        return size(root);
    }

    void put(Key key,Value value){
        root = put(root,key,value);
    }

    Value* search(Key key){
        assert(_contain(root,key));
        root  =  _search(root,key);
        return &root->value;
    }

    void removeMin(){
        assert(root!=NULL);
        root = _removeMin(root);
    }

    void removeMax(){
        assert(root!=NULL);
        root = _removeMax(root);
    }


    void remove(Key key){
        if(root==NULL){
            return ;
        }
        if(!_contain(root,key)){
            return;
        }
        spalytarget = NULL;
        root = _remove(root,key);
        spalytarget = NULL;
    }

    void join(SplayTree<char,char>* tree){
        Node* oroot = tree->root;
        assert(oroot!=NULL);
        assert(root!=NULL);

        Node* s1min = _minNum(oroot);
        Node* s1max = _maxNum(oroot);
        if(s1min->key>_maxNum(root)->key){
            root = _search(root,_maxNum(root)->key);
            root->right = _copy(oroot);
            root->N = 1+size(root->left)+size(root->right);

        }else if(s1max->key<_minNum(root)->key){
            root = _search(root,_minNum(root)->key);
            root->left = _copy(oroot);
            root->N = 1+size(root->left)+size(root->right);
        }else{
            root = _join(oroot);
        }
    }

    bool isEmpty(){
        return root==NULL;
    }

    Key* select(int select){
        assert(select>=0 && select<root->N);
        Node* node = _select(root,0,select);
        return &(node->key);
    }

    //小于key的键数量
    int rank(Key key){
        return _rank(root,key);
    }

    bool check(){
        bool ispassed = true;
        if(!isBST()){
            ispassed = false;
            cout<<" isBST = false"<<endl;
        }
        if(!isSizeConsistent()) {
            ispassed = false;
            cout << " isSizeConsistent = false" << endl;
        }
        if(!isRankConsistent()) {
            ispassed = false;
            cout << " isRankConsistent = false" << endl;
        }
        return ispassed;
    }

    bool isBST(){
        return _isBST(root,NULL,NULL);
    }

    bool isSizeConsistent(){
        return _isSizeConsistent(root);
    }

    bool isRankConsistent() {
        for (int i = 0; i < size(); i++)
            if (i != rank(*select(i))) return false;
        return true;
    }

};

//int main() {
//    SplayTree<char,char> splayTree;
//    char s[] = {'1','2','3','4','5','6','7'};
//    for(int i = 0 ; i< 7;i++){
//        splayTree.put(s[i],s[i]);
////        splayTree.check();
//    }
////    for(int i = 0 ; i< 7;i++){
////        char* v = splayTree.search(s[i]);
////        splayTree.check();
////    }
//
////    for(int i = 0 ; i< 7;i++){
////        splayTree.remove(s[i]);
////        splayTree.check();
////    }
//
//    SplayTree<char,char>* splayTree2 = new SplayTree<char,char>();
//    char s2[] = {'8','9','a','b','c'};
//    for(int i = 0 ; i< 5;i++){
//        (*splayTree2).put(s2[i],s2[i]);
////        splayTree2.check();
//    }
//
////    splayTree.join(splayTree2);
////    delete splayTree2;
////    splayTree.check();
//
//
//
//
//    return 0;
//}

#endif //INC_010_ALGORITHM_SPALYTREE_H
